此题的唯一精髓:搜索模拟
为了模拟方便,这里的3处理为1 , K处理为11 , 1处理为12 , 2处理为13 。
注意
1:大小王不能当对子打出。除了顺子大小王可以当做单张打出。
2:四带二可以用两张相同单牌
唯一的剪枝:当只剩下对子和单张可以打的时候,可以直接扫一遍统计出答案。
再加上最优性剪枝,就可以AC此题了。
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXD = 15;
int t , n , x , y , cnt[ 20 ] , Ans;
bool check( ) {
for( int i = 1 ; i <= MAXD ; i ++ )
if( cnt[ i ] ) return 0;
return 1;
}
void dfs( int step ) {
if( step >= Ans ) return;
if( check( ) ) {
Ans = step;
return;
}
if( cnt[ 14 ] == 1 && cnt[ 15 ] == 1 ) { //火箭
cnt[ 14 ] = cnt[ 15 ] = 0;
dfs( step + 1 );
cnt[ 14 ] = cnt[ 15 ] = 1;
}
int l1 = 0 , l2 = 0 , l3 = 0;
for( int i = 1 ; i <= MAXD - 3 ; i ++ ) { //顺子
l1 = cnt[ i ] >= 1 ? l1 + 1 : 0;
l2 = cnt[ i ] >= 2 ? l2 + 1 : 0;
l3 = cnt[ i ] >= 3 ? l3 + 1 : 0;
if( l1 >= 5 ) { //单顺子
for( int len = 5 ; len <= l1 ; len ++ )
for( int sta = i - l1 + 1 ; sta + len - 1 <= i ; sta ++ ) {
for( int dex = sta ; dex <= sta + len - 1 ; dex ++ )
cnt[ dex ] --;
dfs( step + 1 );
for( int dex = sta ; dex <= sta + len - 1 ; dex ++ )
cnt[ dex ] ++;
}
}
if( l2 >= 3 ) { //双顺子
for( int len = 3 ; len <= l2 ; len ++ )
for( int sta = i - l2 + 1 ; sta + len - 1 <= i ; sta ++ ) {
for( int dex = sta ; dex <= sta + len - 1 ; dex ++ )
cnt[ dex ] -= 2;
dfs( step + 1 );
for( int dex = sta ; dex <= sta + len - 1 ; dex ++ )
cnt[ dex ] += 2;
}
}
if( l3 >= 2 ) { //三顺子
for( int len = 2 ; len <= l3 ; len ++ )
for( int sta = i - l3 + 1 ; sta + len - 1 <= i ; sta ++ ) {
for( int dex = sta ; dex <= sta + len - 1 ; dex ++ )
cnt[ dex ] -= 3;
dfs( step + 1 );
for( int dex = sta ; dex <= sta + len - 1 ; dex ++ )
cnt[ dex ] += 3;
}
}
}
for( int i = 1 ; i <= MAXD ; i ++ ) {
if( cnt[ i ] >= 3 ) {
cnt[ i ] -= 3;
dfs( step + 1 );//三张牌
for( int dex = 1 ; dex <= MAXD ; dex ++ )
if( cnt[ dex ] && dex != i ) { //三带二
if( cnt[ dex ] >= 2 ) {
cnt[ dex ] -= 2;
dfs( step + 1 );
cnt[ dex ] += 2;
}
if( cnt[ dex ] >= 1 ) { //三代一
cnt[ dex ] --;
dfs( step + 1 );
cnt[ dex ] ++;
}
}
cnt[ i ] += 3;
}
if( cnt[ i ] >= 4 ) {
cnt[ i ] -= 4;//炸弹
dfs( step + 1 );
for( int dex1 = 1 ; dex1 <= MAXD ; dex1 ++ )
if( cnt[ dex1 ] && dex1 != i )
for( int dex2 = dex1 ; dex2 <= MAXD ; dex2 ++ )
if( cnt[ dex2 ] && dex2 != i ) {
if( cnt[ dex1 ] >= 1 && cnt[ dex2 ] >= 1 ) {//四代2张单牌
cnt[ dex1 ] -- , cnt[ dex2 ] --;
dfs( step + 1 );
cnt[ dex1 ] ++ , cnt[ dex2 ] ++;
}
if( cnt[ dex1 ] >= 2 && cnt[ dex2 ] >= 2 ) { //四代2双对子
cnt[ dex1 ] -= 2 , cnt[ dex2 ] -= 2;
dfs( step + 1 );
cnt[ dex1 ] += 2 , cnt[ dex2 ] += 2;
}
}
cnt[ i ] += 4;
}
}
int res = 0;
for( int i = 1 ; i <= MAXD ; i ++ )
if( cnt[ i ] ) res ++;
Ans = min( Ans , step + res ); //唯一的剪枝
}
int main( ) {
scanf("%d %d",&t,&n);
while( t -- ) {
Ans = n;
for( int i = 1 ; i <= MAXD ; i ++ ) cnt[ i ] = 0;
for( int i = 1 ; i <= n ; i ++ ) {
scanf("%d %d",&x,&y);
if( x == 0 ) cnt[ 13 + y ] ++;
if( x == 1 ) cnt[ 12 ] ++;
if( x == 2 ) cnt[ 13 ] ++;
if( x >= 3 ) cnt[ x - 2 ] ++;
}
//for( int i = 1 ; i <= 15 ; i ++ )
// printf("%d %d\n",i,cnt[ i ]);
dfs( 0 );
printf("%d\n", Ans );
}
return 0;
}